package com.wtgroup.demo.mianshi.算法.排序;

import com.wtgroup.demo.common.util.Tools;

import java.util.Arrays;

/**
 * 迭代方式归并排序
 *
 * @author dafei
 * @version 0.1
 * @date 2021/4/16 18:35
 */
public class MergeSortIter {

    public static void main(String[] args) {
        int[] arr = {21, 4, 5, 2, 6, 8, 2, 1, 8};
        merge(arr);
        Tools.printArray(arr);
    }

    // TODO 未完成
    public static void merge(int[] arr) {
        int n = arr.length;
        int step = 1; // 最大 n

        while (step < n) { // 上次的 step 达到了 n, 则整个数组已经合并完了, 有序的了
            step *= 2;
            for (int i = 0; i < n; i += step) {
                // 切分两部分归并
                int mid = i + step - 1;
                combine(i, Math.min(i + step - 1, n-1), arr);
            }
        }
    }

    private static void combine(int left, int right, int[] arr) {
        int mid = left + ((right - left) >> 1);
        // left~mid, mid+1~right
        int[] tmp = new int[right - left + 1];
        int i = left, j = mid+1;
        int k = 0;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                tmp[k++] = arr[i++];
            } else {
                tmp[k++] = arr[j++];
            }
        }
        while (i <= mid) {
            tmp[k++] = arr[i++];
        }
        while (j <= right) {
            tmp[k++] = arr[j++];
        }
        for (int l = 0, m=left; l < tmp.length; l++,m++) {
            arr[m] = tmp[l];
        }
    }


}
